Access control lists (“ACLs”) may be utilized in conjunction with file storage systems to specify access rights for file system objects, such as files and folders. The access rights may specify whether a given user is allowed to perform certain file operations. The access rights may also specify the extent to which the user is allowed to perform certain file operations. For example, an ACL may specify that a user U1 has read-only access to a file F1 and another user U2 has read-write access to the same file F1. Each file system object may have an associated ACL.
Each ACL may include one or more access control entries (“ACEs”). Each ACE can define the access rights for a particular user or group of users. When a user attempts an operation on a file system object, the file system can check the corresponding ACL to see if the user has the necessary access rights to perform the operation. If the user has the necessary access rights, the file system may permit access to the file system object. If the user does not have the necessary access rights, the file system may deny access to the file system object.
Conventionally, the ACL resides on disk as part of the metadata associated with the file system object. Consider, for example, the following sequence of operations where a user adds a new ACE to an ACL or modifies an existing ACE within the ACL. First, the file system retrieves the ACL from disk in order to check whether the user has permission to retrieve the ACL. If the user does have permission to retrieve the ACL, then the file system retrieves the ACL a second time in order to check whether the user has permission to add a new ACE or modify the existing ACE. If the user does have permission to add a new ACE or modify the existing ACE, the file system adds the new ACE or modifies the existing ACE to disk. Upon writing the ACL to disk, the file system retrieves the ACL a third time in order to display the modified ACL to the user. In this example, the ACL is retrieve three times, and the disk is accessed four times (e.g., three ACL gets and one ACL write).
In order to reduce the number of disk accesses, the file system may cache the ACL in memory. In the above example, caching may reduce the number of ACL gets from three to two. In cases of a recursive ACL operation where the ACLs associated with an entire tree are modified, the number of disk accesses can be reduced to one. This can happen because when the ACL of a given folder is modified, the ACLs of each subfolder and file contained in the folder are also flushed to disk.
Conventional caching solutions suffer are inefficient because ACLs can vary in size. In particular, the size of an ACL may be determined from the number of ACEs contained in the ACL. However, in prevalent caching models, such as those utilized in UNIX/LINUX and other suitable file systems, a cache line is a fixed block or chunk of memory that represents a corresponding on-disk image. As a result, one approach is to set the size of the cache line to correspond to the largest possible ACL. Although this approach ensures that every cache line can store every ACL, this approach wastes memory where the cache lines store ACLs less than the maximum size.
In order to address the drawbacks of the fixed sized cache line, another approach utilizes multiple cache line classes having cache lines of varying sizes. Each cache line class may represent a landmark number of ACEs (e.g., 2, 4, 6, 8, 16, 32, etc.). When an ACL is cached from disk, the file system stores the ACL in the nearest sized cache link equal to or greater than the size of the ACL. For example, if an ACL containing fifteen ACEs is cached from disk, the file system may store the ACL into a cache line corresponding to the cache line class that can hold sixteen ACEs.
Although having multiple cache line classes provides some improvement over cache lines of a single size, difficulty can arise when defining the number of cache lines for each class. In particular, when multiple cache line classes of ACL are defined, the number of cache lines for each class is defined at compilation time. However, due to varying user behavior, classes that have a fewer number of cache lines may be highly utilized, while classes having a higher number of cache lines may be sparsely utilized. These unutilized cache lines account for wasted space in memory.
It is with respect to these and other considerations that the disclosure made herein is presented.